#include <iostream>
#include <vector>
#include <queue>
#include <climits> // 用于INT_MAX
using namespace std;

// 定义顶点的访问状态
const int RED = 2;
const int GREEN = 1;
const int WHITE = 0;

// 定义优先队列的节点类
struct QueueNode {
    int node, path; // 节点编号，最短路径长度
    QueueNode(int n, int p) : node(n), path(p) {}
    // 重载比较运算符，用于优先队列
    bool operator>(const QueueNode& other) const {
        return path > other.path;
    }
};

// Dijkstra算法计算最短路径（使用优先队列）
int findAllShortestPath(int n, const vector<vector<int>>& edges, int src) {
    // 边权集转邻接表，提高邻接点搜索时的效率
    vector<vector<pair<int, int>>> linkTable(n + 1);
    for (const auto& ed : edges) {
        linkTable[ed[0]].emplace_back(ed[1], ed[2]);
    }

    // dist[x]: 保存起点到 x 的最短路径长度，初始值为无穷大
    vector<int> dist(n + 1, INT_MAX);
    // visit[x]表示 x 的访问状态
    vector<int> visit(n + 1, WHITE);

    // 初始时只有起点被访问到，设置路径长度为0
    visit[src] = GREEN;
    dist[src] = 0;

    // 创建优先队列
    priority_queue<QueueNode, vector<QueueNode>, greater<QueueNode>> pq;
    pq.emplace(src, 0);

    // 执行Dijkstra搜索最短路径
    while (!pq.empty()) {
        // 从优先队列中取出下一个路径最短顶点
        QueueNode sn = pq.top();
        pq.pop();
        int s = sn.node;

        // 过滤掉已经处理过的顶点
        if (visit[s] == RED) continue;

        // 将顶点标记为红点，并作为当前搜索点
        visit[s] = RED;

        // 枚举当前顶点 s 的邻接路径，发现新的路径并更新优先队列
        for (const auto& [t, w] : linkTable[s]) {
            if (visit[t] != RED) {
                // 计算从起点经过s到达t的路径长度
                int d = dist[s] + w;
                if (d < dist[t]) {
                    // 找到更短路径，加入优先队列
                    dist[t] = d;
                    visit[t] = GREEN;
                    pq.emplace(t, d);
                }
            }
        }
    }

    // 输出结果并返回
    int ans = -1;
    cout << "所有的顶点路径信息:" << endl;
    for (int i = 1; i <= n; i++) {
        cout << "目标顶点 " << i << " -> " << dist[i] << endl;
        ans = max(ans, dist[i]);
    }
    return ans;
}

int main() {
    vector<vector<int>> edges = {
        {1, 2, 2}, {1, 5, 8}, {1, 4, 3}, {2, 3, 5}, {3, 5, 1}, {4, 3, 2}, {4, 5, 6}
    };
    int n = 5, src = 1;
    int ans = findAllShortestPath(n, edges, src);
    cout << "搜索完毕，最远顶点路径为：" << ans << endl;
    return 0;
}